package com.lxl.quick;

import java.util.Arrays;

/**
 * @Classname QuickSort
 * @Description 快速排序
 * 时间复杂度 O(N * logN)
 * 不稳定
 * @Date 2021/8/18 9:25
 * @Created by LXLDEMO
 */
public class QuickSort {

    public static void main(String[] args) {
        // 测试数据
        int arr[] = {2,4,3,1,6,5};
        // 快速排序
        quickSort(arr,arr.length);
    }

    /**
     * 快速排序
     * @param arr
     * @param len
     */
    public static void quickSort(int[] arr, int len){
        System.out.println("初始数据 " + Arrays.toString(arr) + "\n\n");
        quickSort(arr,0,len-1);
    }

    /**
     * 快速排序
     * @param arr
     * @param low
     * @param high
     */
    public static void quickSort(int[] arr,int low,int high) {

        int mid;
        if (low<high){
            mid = partition(arr,low,high); // 进行分割操作并返回基准元素
            quickSort(arr,low,mid -1); // 右区间递归快速排序
            quickSort(arr,mid+1,high); // 左区间递归快速排序
        }
    }

    /**
     * 返回基准
     * @param arr
     * @param low
     * @param high
     * @return
     */
    public static int partition(int[] arr,int low, int high){
        System.out.println("开始下标 "+ low);
        System.out.println("结束下标 "+ high);

        int i = low; // 待处理第一个下标
        int j = high; // 待处理最后一个下标
        // 分界值
        int pivot = arr[low];
        System.out.println("分界值 [" + pivot + "]");
        while (i<j){

            // 从右往左扫描  跳出循环：j==i 或 arr[j] <= arr[pivot]
            while (i<j && arr[j]>pivot){
                j--;
            }

            // arr[i] 和 arr[j] 交换后，i右移一位
            if (i<j){
                swap(arr,i,j);
                System.out.println("右侧遍历 本次交换结果"+ Arrays.toString(arr));
                i++;
            }

            // 从左往右扫描 跳出循环 i==j 或 arr[i]>pivot
            while (i<j && arr[i]<=pivot){
                i++;
            }

            // arr[i] 和 arr[j] 交换后，j左移一位
            if (i<j){
                swap(arr,i,j);
                System.out.println("左侧遍历 本次交换结果" + Arrays.toString(arr));
                j--;
            }
        }
        // 返回最终划分完成后基准匀速所在的位置 i==j
        System.out.println("新基准下标 " + i + "\n");
        return i;
    }



    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}
